package com.demo.algorithm.bfs03;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * Description: BFS——解开密码锁的最少次数/打开转盘锁 （LeetCode752）
 *
 * @Date: 2021/6/4 8:30
 * @Author: zsyoung@qq.com
 */
public class PasswordLock {
    //粗略版
    void BFS(String target) {
        Queue<String> q = new LinkedList<>();
        q.offer("0000");

        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String cur = q.poll();
                /*判断是否达到终点*/
                System.out.println(cur);

                for (int j = 0; j < 4; j++) {
                    String up = plusOne(cur, j);
                    String down = minusOne(cur, j);
                    q.offer(up);
                    q.offer(down);
                }
            }
            /*在这里增加步数*/
        }
        return;
    }

    //改进版
    private static int openLock(String[] deadends, String target) {
        Set<String> deads = new HashSet<>(); //记录需要跳过的死亡密码
        for (String s : deadends) {
            deads.add(s);
        }
        Set<String> visited = new HashSet<>(); //记录已经穷举过的密码，防止走回头路
        Queue<String> q = new LinkedList<>();

        int step = 0; // 从起点开始启动广度优先搜索
        q.offer("0000");
        visited.add("0000");

        while (!q.isEmpty()) {
            int size = q.size();
            /*将当前队列中的所有节点向周围扩散*/
            for (int i = 0; i < size; i++) {
                String cur = q.poll();

                /*判断是否达到终点*/
                if (deads.contains(cur))
                    continue;
                if (target.equals(cur))
                    return step;

                /*将一个节点的未遍历相邻节点加入队列*/
                for (int j = 0; j < 4; j++) {
                    String up = plusOne(cur, j);
                    if (!visited.contains(up)) {
                        q.offer(up);
                        visited.add(up);
                    }
                    String down = minusOne(cur, j);
                    if (!visited.contains(down)) {
                        q.offer(down);
                        visited.add(down);
                    }
                }
            }
            /*在这里增加步数*/
            step++;
        }
        /*如果穷举完都没有找到目标密码，那就是找不到了*/
        return -1;
    }


    /**
     * 将s[j]向下拨动一次
     *
     * @param s
     * @param j
     * @return
     */
    private static String minusOne(String s, int j) {
        char[] ch = s.toCharArray();
        if (ch[j] == '0') {
            ch[j] = '9';
        } else {
            ch[j] -= 1;
        }
        return new String(ch);
    }

    /**
     * 将s[j]向上拨动一次
     *
     * @param s
     * @param j
     * @return
     */
    private static String plusOne(String s, int j) {
        char[] ch = s.toCharArray();
        if (ch[j] == '9') {
            ch[j] = '0';
        } else {
            ch[j] += 1;
        }
        return new String(ch);
    }

    public static void main(String[] args) {
        String[] deadends = {"8888"};
        String target = "0009";
        System.out.println("openLock(deadends,target) = " + openLock(deadends, target));
    }
}
